# O(n^2)
# class Solution(object):
#     def maxSumTwoNoOverlap(self, nums, firstLen, secondLen):
#         n = len(nums)
#         now_f = sum(nums[:firstLen])
#         now_s = sum(nums[firstLen: firstLen + secondLen])
#         max_v = now_f + now_s
#         for j in range(firstLen, n - secondLen):
#             now_s = now_s - nums[j] + nums[j + secondLen]
#             max_v = max(max_v, now_f + now_s)
#         for i in range(n - firstLen):
#             now_f = now_f - nums[i] + nums[i + firstLen]
#             if i + 1 >= secondLen:
#                 now_s = sum(nums[:secondLen])
#                 max_v = max(max_v, now_f + now_s)
#                 for j in range(i + 1 - secondLen):
#                     now_s = now_s - nums[j] + nums[j + secondLen]
#                     max_v = max(max_v, now_f + now_s)
#             if i + firstLen < n - secondLen:
#                 k = i + firstLen + 1
#                 now_s = sum(nums[k: k + secondLen])
#                 max_v = max(max_v, now_f + now_s)
#                 for j in range(k, n - secondLen):
#                     now_s = now_s - nums[j] + nums[j + secondLen]
#                     max_v = max(max_v, now_f + now_s)
#         return max_v

# 前缀和+动态规划
class Solution(object):
    def maxSumTwoNoOverlap(self, nums, firstLen, secondLen):
        n = len(nums)
        for i in range(n - 1):
            nums[i + 1] += nums[i]
        L_max = nums[firstLen - 1]
        M_max = nums[secondLen - 1]
        ans = nums[firstLen + secondLen - 1]
        for i in range(firstLen + secondLen, n):
            L_max = max(L_max, nums[i - secondLen] - nums[i - firstLen - secondLen])
            M_max = max(M_max, nums[i - firstLen] - nums[i - firstLen - secondLen])
            ans = max(ans, L_max + nums[i] - nums[i - secondLen], M_max + nums[i] - nums[i - firstLen])
        return ans


data = Solution()
nums = [3,8,1,3,2,1,8,9,0]
firstLen = 3
secondLen = 2
print(data.maxSumTwoNoOverlap(nums, firstLen, secondLen))
